﻿using System;
using System.Net;
using System.Windows;
using System.Windows.Controls;
using System.Windows.Documents;
using System.Windows.Ink;
using System.Windows.Input;
using System.Windows.Media;
using System.Windows.Media.Animation;
using System.Windows.Shapes;
using System.Collections.Generic;

namespace GameEngine.Libs
{
    /**
     * A description of an implementation that can find a path from one 
     * location on a tile map to another based on information provided
     * by that tile map.
     * 
     * @see TileBasedMap
     * @author Kevin Glass
     */
    public interface PathFinder
    {
        /**
         * Find a path from the starting location provided (sx,sy) to the target
         * location (tx,ty) avoiding blockages and attempting to honour costs 
         * provided by the tile map.
         * 
         * @param mover The entity that will be moving along the path. This provides
         * a place to pass context information about the game entity doing the moving, e.g.
         * can it fly? can it swim etc.
         * 
         * @param sx The x coordinate of the start location
         * @param sy The y coordinate of the start location
         * @param tx The x coordinate of the target location
         * @param ty Teh y coordinate of the target location
         * @return The path found from start to end, or null if no path can be found.
         */
        Path findPath(Mover mover, int sx, int sy, int tx, int ty);
    }

    /**
     * The description of a class providing a cost for a given tile based
     * on a target location and entity being moved. This heuristic controls
     * what priority is placed on different tiles during the search for a path
     * 
     * @author Kevin Glass
     */
    public interface AStarHeuristic
    {

        /**
         * Get the additional heuristic cost of the given tile. This controls the
         * order in which tiles are searched while attempting to find a path to the 
         * target location. The lower the cost the more likely the tile will
         * be searched.
         * 
         * @param map The map on which the path is being found
         * @param mover The entity that is moving along the path
         * @param x The x coordinate of the tile being evaluated
         * @param y The y coordinate of the tile being evaluated
         * @param tx The x coordinate of the target location
         * @param ty Teh y coordinate of the target location
         * @return The cost associated with the given tile
         */
        float getCost(TileBasedMap map, Mover mover, int x, int y, int tx, int ty);
    }

    /**
     * A tagging interface for an object representing the entity in the game that
     * is going to moving along the path. This allows us to pass around entity/state
     * information to determine whether a particular tile is blocked, or how much
     * cost to apply on a particular tile.
     * 
     * For instance, a Mover might represent a tank or plane on a game map. Passing round
     * this entity allows us to determine whether rough ground on a map should effect
     * the unit's cost for moving through the tile.
     * 
     * @author Kevin Glass
     */
    public interface Mover
    {

    }

    /**
     * The description for the data we're pathfinding over. This provides the contract
     * between the data being searched (i.e. the in game map) and the path finding
     * generic tools
     * 
     * @author Kevin Glass
     */
    public interface TileBasedMap
    {
        /**
         * Get the width of the tile map. The slightly odd name is used
         * to distiguish this method from commonly used names in game maps.
         * 
         * @return The number of tiles across the map
         */
        int getWidthInTiles();

        /**
         * Get the height of the tile map. The slightly odd name is used
         * to distiguish this method from commonly used names in game maps.
         * 
         * @return The number of tiles down the map
         */
        int getHeightInTiles();

        /**
         * Notification that the path finder visited a given tile. This is 
         * used for debugging new heuristics.
         * 
         * @param x The x coordinate of the tile that was visited
         * @param y The y coordinate of the tile that was visited
         */
        void pathFinderVisited(int x, int y);

        /**
         * Check if the given location is blocked, i.e. blocks movement of 
         * the supplied mover.
         * 
         * @param mover The mover that is potentially moving through the specified
         * tile.
         * @param x The x coordinate of the tile to check
         * @param y The y coordinate of the tile to check
         * @return True if the location is blocked
         */
        bool blocked(Mover mover, int x, int y);

        /**
         * Get the cost of moving through the given tile. This can be used to 
         * make certain areas more desirable. A simple and valid implementation
         * of this method would be to return 1 in all cases.
         * 
         * @param mover The mover that is trying to move across the tile
         * @param sx The x coordinate of the tile we're moving from
         * @param sy The y coordinate of the tile we're moving from
         * @param tx The x coordinate of the tile we're moving to
         * @param ty The y coordinate of the tile we're moving to
         * @return The relative cost of moving across the given tile
         */
        float getCost(Mover mover, int sx, int sy, int tx, int ty);
    }

    /**
     * A path finder implementation that uses the AStar heuristic based algorithm
     * to determine a path. 
     * 
     * @author Kevin Glass
     */
    public class AStarPathFinder : PathFinder
    {

        /** The set of nodes that have been searched through */
        private List<Node> closed = new List<Node>();
        /** The set of nodes that we do not yet consider fully searched */
        private SortedList open = new SortedList();

        /** The map being searched */
        private TileBasedMap map;
        /** The maximum depth of search we're willing to accept before giving up */
        private int maxSearchDistance;

        /** The complete set of nodes across the map */
        private Node[][] nodes;
        /** True if we allow diaganol movement */
        private bool allowDiagMovement;
        /** The heuristic we're applying to determine which nodes to search first */
        private AStarHeuristic heuristic;

        /**
         * Create a path finder with the default heuristic - closest to target.
         * 
         * @param map The map to be searched
         * @param maxSearchDistance The maximum depth we'll search before giving up
         * @param allowDiagMovement True if the search should try diaganol movement
         */
        public AStarPathFinder(TileBasedMap map, int maxSearchDistance, bool allowDiagMovement)
        {
            initialize(map, maxSearchDistance, allowDiagMovement, new ClosestHeuristic());
        }

        /**
         * Create a path finder 
         * 
         * @param heuristic The heuristic used to determine the search order of the map
         * @param map The map to be searched
         * @param maxSearchDistance The maximum depth we'll search before giving up
         * @param allowDiagMovement True if the search should try diaganol movement
         */
        public AStarPathFinder(TileBasedMap map, int maxSearchDistance,
                               bool allowDiagMovement, AStarHeuristic heuristic)
        {
            initialize(map, maxSearchDistance, allowDiagMovement, heuristic);
        }

        void initialize(TileBasedMap map, int maxSearchDistance,
                               bool allowDiagMovement, AStarHeuristic heuristic)
        {
            this.heuristic = heuristic;
            this.map = map;
            this.maxSearchDistance = maxSearchDistance;
            this.allowDiagMovement = allowDiagMovement;

            //nodes = new Node[map.getWidthInTiles()][map.getHeightInTiles()]{};
            List<Node[]> nodesList = new List<Node[]>();
            for (int x = 0; x < map.getWidthInTiles(); x++)
            {
                List<Node> nodeList = new List<Node>();
                for (int y = 0; y < map.getHeightInTiles(); y++)
                {
                    nodeList.Add(new Node(x, y));
                    //nodes[x][y] = new Node(x,y);
                }
                nodesList.Add(nodeList.ToArray());
            }
            nodes = nodesList.ToArray();
        }

        /**
         * @see PathFinder#findPath(Mover, int, int, int, int)
         */
        public Path findPath(Mover mover, int sx, int sy, int tx, int ty)
        {
            // easy first check, if the destination is blocked, we can't get there

            if (map.blocked(mover, tx, ty))
            {
                return null;
            }

            // initial state for A*. The closed group is empty. Only the starting

            // tile is in the open list and it'e're already there
            nodes[sx][sy].cost = 0;
            nodes[sx][sy].depth = 0;
            closed.Clear();
            open.clear();
            open.add(nodes[sx][sy]);

            nodes[tx][ty].parent = null;

            // while we haven'n't exceeded our max search depth
            int maxDepth = 0;
            while ((maxDepth < maxSearchDistance) && (open.size() != 0))
            {
                // pull out the first node in our open list, this is determined to 

                // be the most likely to be the next step based on our heuristic

                Node current = getFirstInOpen();
                if (current == nodes[tx][ty])
                {
                    break;
                }

                removeFromOpen(current);
                addToClosed(current);

                // search through all the neighbours of the current node evaluating

                // them as next steps

                for (int x = -1; x < 2; x++)
                {
                    for (int y = -1; y < 2; y++)
                    {
                        // not a neighbour, its the current tile

                        if ((x == 0) && (y == 0))
                        {
                            continue;
                        }

                        // if we're not allowing diaganol movement then only 

                        // one of x or y can be set

                        if (!allowDiagMovement)
                        {
                            if ((x != 0) && (y != 0))
                            {
                                continue;
                            }
                        }

                        // determine the location of the neighbour and evaluate it

                        int xp = x + current.x;
                        int yp = y + current.y;

                        if (isValidLocation(mover, sx, sy, xp, yp))
                        {
                            // the cost to get to this node is cost the current plus the movement

                            // cost to reach this node. Note that the heursitic value is only used

                            // in the sorted open list

                            float nextStepCost = current.cost + getMovementCost(mover, current.x, current.y, xp, yp);
                            Node neighbour = nodes[xp][yp];
                            map.pathFinderVisited(xp, yp);

                            // if the new cost we've determined for this node is lower than 

                            // it has been previously makes sure the node hasn'e've
                            // determined that there might have been a better path to get to

                            // this node so it needs to be re-evaluated

                            if (nextStepCost < neighbour.cost)
                            {
                                if (inOpenList(neighbour))
                                {
                                    removeFromOpen(neighbour);
                                }
                                if (inClosedList(neighbour))
                                {
                                    removeFromClosed(neighbour);
                                }
                            }

                            // if the node hasn't already been processed and discarded then

                            // reset it's cost to our current cost and add it as a next possible

                            // step (i.e. to the open list)

                            if (!inOpenList(neighbour) && !(inClosedList(neighbour)))
                            {
                                neighbour.cost = nextStepCost;
                                neighbour.heuristic = getHeuristicCost(mover, xp, yp, tx, ty);
                                maxDepth = Math.Max(maxDepth, neighbour.setParent(current));
                                addToOpen(neighbour);
                            }
                        }
                    }
                }
            }

            // since we'e've run out of search 
            // there was no path. Just return null

            if (nodes[tx][ty].parent == null)
            {
                return null;
            }

            // At this point we've definitely found a path so we can uses the parent

            // references of the nodes to find out way from the target location back

            // to the start recording the nodes on the way.

            Path path = new Path();
            Node target = nodes[tx][ty];
            while (target != nodes[sx][sy])
            {
                path.prependStep(target.x, target.y);
                target = target.parent;
            }
            path.prependStep(sx, sy);

            // thats it, we have our path 

            return path;
        }

        /**
         * Get the first element from the open list. This is the next
         * one to be searched.
         * 
         * @return The first element in the open list
         */
        protected Node getFirstInOpen()
        {
            return (Node)open.first();
        }

        /**
         * Add a node to the open list
         * 
         * @param node The node to be added to the open list
         */
        protected void addToOpen(Node node)
        {
            open.add(node);
        }

        /**
         * Check if a node is in the open list
         * 
         * @param node The node to check for
         * @return True if the node given is in the open list
         */
        protected bool inOpenList(Node node)
        {
            return open.contains(node);
        }

        /**
         * Remove a node from the open list
         * 
         * @param node The node to remove from the open list
         */
        protected void removeFromOpen(Node node)
        {
            open.remove(node);
        }

        /**
         * Add a node to the closed list
         * 
         * @param node The node to add to the closed list
         */
        protected void addToClosed(Node node)
        {
            closed.Add(node);
        }

        /**
         * Check if the node supplied is in the closed list
         * 
         * @param node The node to search for
         * @return True if the node specified is in the closed list
         */
        protected bool inClosedList(Node node)
        {
            return closed.Contains(node);
        }

        /**
         * Remove a node from the closed list
         * 
         * @param node The node to remove from the closed list
         */
        protected void removeFromClosed(Node node)
        {
            closed.Remove(node);
        }

        /**
         * Check if a given location is valid for the supplied mover
         * 
         * @param mover The mover that would hold a given location
         * @param sx The starting x coordinate
         * @param sy The starting y coordinate
         * @param x The x coordinate of the location to check
         * @param y The y coordinate of the location to check
         * @return True if the location is valid for the given mover
         */
        protected bool isValidLocation(Mover mover, int sx, int sy, int x, int y)
        {
            bool invalid = (x < 0) || (y < 0) || (x >= map.getWidthInTiles()) || (y >= map.getHeightInTiles());

            if ((!invalid) && ((sx != x) || (sy != y)))
            {
                invalid = map.blocked(mover, x, y);
            }

            return !invalid;
        }

        /**
         * Get the cost to move through a given location
         * 
         * @param mover The entity that is being moved
         * @param sx The x coordinate of the tile whose cost is being determined
         * @param sy The y coordiante of the tile whose cost is being determined
         * @param tx The x coordinate of the target location
         * @param ty The y coordinate of the target location
         * @return The cost of movement through the given tile
         */
        public float getMovementCost(Mover mover, int sx, int sy, int tx, int ty)
        {
            return map.getCost(mover, sx, sy, tx, ty);
        }

        /**
         * Get the heuristic cost for the given location. This determines in which 
         * order the locations are processed.
         * 
         * @param mover The entity that is being moved
         * @param x The x coordinate of the tile whose cost is being determined
         * @param y The y coordiante of the tile whose cost is being determined
         * @param tx The x coordinate of the target location
         * @param ty The y coordinate of the target location
         * @return The heuristic cost assigned to the tile
         */
        public float getHeuristicCost(Mover mover, int x, int y, int tx, int ty)
        {
            return heuristic.getCost(map, mover, x, y, tx, ty);
        }

        /**
         * A simple sorted list
         *
         * @author kevin
         */
        private class SortedList
        {
            /** The list of elements */
            private List<Object> list = new List<Object>();

            /**
             * Retrieve the first element from the list
             *  
             * @return The first element from the list
             */
            public Object first()
            {
                return list[0];
            }

            /**
             * Empty the list
             */
            public void clear()
            {
                list.Clear();
            }

            /**
             * Add an element to the list - causes sorting
             * 
             * @param o The element to add
             */
            public void add(Object o)
            {
                list.Add(o);
                list.Sort();
            }

            /**
             * Remove an element from the list
             * 
             * @param o The element to remove
             */
            public void remove(Object o)
            {
                list.Remove(o);
            }

            /**
             * Get the number of elements in the list
             * 
             * @return The number of element in the list
             */
            public int size()
            {
                return list.Count;
            }

            /**
             * Check if an element is in the list
             * 
             * @param o The element to search for
             * @return True if the element is in the list
             */
            public bool contains(Object o)
            {
                return list.Contains(o);
            }
        }

        /**
         * A single node in the search graph
         */
        protected class Node : IComparable
        {
            /** The x coordinate of the node */
            public int x;
            /** The y coordinate of the node */
            public int y;
            /** The path cost for this node */
            public float cost;
            /** The parent of this node, how we reached it in the search */
            public Node parent;
            /** The heuristic cost of this node */
            public float heuristic;
            /** The search depth of this node */
            public int depth;

            /**
             * Create a new node
             * 
             * @param x The x coordinate of the node
             * @param y The y coordinate of the node
             */
            public Node(int x, int y)
            {
                this.x = x;
                this.y = y;
            }

            /**
             * Set the parent of this node
             * 
             * @param parent The parent node which lead us to this node
             * @return The depth we have no reached in searching
             */
            public int setParent(Node parent)
            {
                depth = parent.depth + 1;
                this.parent = parent;

                return depth;
            }

            /**
             * @see Comparable#compareTo(Object)
             */
            public int CompareTo(Object other)
            {
                Node o = (Node)other;

                float f = heuristic + cost;
                float of = o.heuristic + o.cost;

                if (f < of)
                {
                    return -1;
                }
                else if (f > of)
                {
                    return 1;
                }
                else
                {
                    return 0;
                }
            }
        }
    }

    /**
 * A path determined by some path finding algorithm. A series of steps from
 * the starting location to the target location. This includes a step for the
 * initial location.
 * 
 * @author Kevin Glass
 */
    public class Path
    {
        /** The list of steps building up this path */
        private List<Step> steps = new List<Step>();

        /**
         * Create an empty path
         */
        public Path()
        {

        }

        /**
         * Get the length of the path, i.e. the number of steps
         * 
         * @return The number of steps in this path
         */
        public int getLength()
        {
            return steps.Count;
        }

        /**
         * Get the step at a given index in the path
         * 
         * @param index The index of the step to retrieve. Note this should
         * be >= 0 and < getLength();
         * @return The step information, the position on the map.
         */
        public Step getStep(int index)
        {
            return (Step)steps[index];
        }

        /**
         * Get the x coordinate for the step at the given index
         * 
         * @param index The index of the step whose x coordinate should be retrieved
         * @return The x coordinate at the step
         */
        public int getX(int index)
        {
            return getStep(index).x;
        }

        /**
         * Get the y coordinate for the step at the given index
         * 
         * @param index The index of the step whose y coordinate should be retrieved
         * @return The y coordinate at the step
         */
        public int getY(int index)
        {
            return getStep(index).y;
        }

        /**
         * Append a step to the path.  
         * 
         * @param x The x coordinate of the new step
         * @param y The y coordinate of the new step
         */
        public void appendStep(int x, int y)
        {
            steps.Add(new Step(x, y));
        }

        /**
         * Prepend a step to the path.  
         * 
         * @param x The x coordinate of the new step
         * @param y The y coordinate of the new step
         */
        public void prependStep(int x, int y)
        {
            steps.Insert(0, new Step(x, y));
        }

        /**
         * Check if this path contains the given step
         * 
         * @param x The x coordinate of the step to check for
         * @param y The y coordinate of the step to check for
         * @return True if the path contains the given step
         */
        public bool contains(int x, int y)
        {
            return steps.Contains(new Step(x, y));
        }

        /**
         * A single step within the path
         * 
         * @author Kevin Glass
         */
        public class Step
        {
            /** The x coordinate at the given step */
            public int x;
            /** The y coordinate at the given step */
            public int y;

            /**
             * Create a new step
             * 
             * @param x The x coordinate of the new step
             * @param y The y coordinate of the new step
             */
            public Step(int x, int y)
            {
                this.x = x;
                this.y = y;
            }

            /**
             * Get the x coordinate of the new step
             * 
             * @return The x coodindate of the new step
             */
            public int getX()
            {
                return x;
            }

            /**
             * Get the y coordinate of the new step
             * 
             * @return The y coodindate of the new step
             */
            public int getY()
            {
                return y;
            }

            /**
             * @see Object#hashCode()
             */
            public int hashCode()
            {
                return x * y;
            }

            /**
             * @see Object#equals(Object)
             */
            public bool equals(Object other)
            {
                if (other is Step)
                {
                    Step o = (Step)other;

                    return (o.x == x) && (o.y == y);
                }

                return false;
            }
        }
    }

    /**
     * A heuristic that uses the tile that is closest to the target
     * as the next best tile.
     * 
     * @author Kevin Glass
     */
    class ClosestHeuristic : AStarHeuristic
    {
        /**
         * @see AStarHeuristic#getCost(TileBasedMap, Mover, int, int, int, int)
         */
        public float getCost(TileBasedMap map, Mover mover, int x, int y, int tx, int ty)
        {
            float dx = tx - x;
            float dy = ty - y;

            float result = (float)(Math.Sqrt((dx * dx) + (dy * dy)));

            return result;
        }
    }
}
